package com.fzn3.day01;


import org.junit.Test;
import org.junit.jupiter.api.DisplayName;

import java.util.Arrays;

import static com.fzn3.day01.BinarySearch.*;
import static org.junit.Assert.assertEquals;

/**
 * @program: DataStructure
 * @author: fzn
 * 描述：测试二分查找
 * @create: 2023/3/3 15:38
 **/
public class TestBinarySearch {

    @Test
    @DisplayName("找到")
    public void test1() {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(0, binarySearchBase(arr, 7));
        assertEquals(1, binarySearchBase(arr, 13));
        assertEquals(2, binarySearchBase(arr, 21));
        assertEquals(3, binarySearchBase(arr, 30));
        assertEquals(4, binarySearchBase(arr, 38));
        assertEquals(5, binarySearchBase(arr, 44));
        assertEquals(6, binarySearchBase(arr, 52));
        assertEquals(7, binarySearchBase(arr, 53));
    }

    @Test
    @DisplayName("没找到")
    public void test2() {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(-1, binarySearchBase(arr, 0));
        assertEquals(-1, binarySearchBase(arr, 15));
        assertEquals(-1, binarySearchBase(arr, 60));
    }

    @Test
    @DisplayName("找到")
    public void test3() {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(0, binarySearchAlternative(arr, 7));
        assertEquals(1, binarySearchAlternative(arr, 13));
        assertEquals(2, binarySearchAlternative(arr, 21));
        assertEquals(3, binarySearchAlternative(arr, 30));
        assertEquals(4, binarySearchAlternative(arr, 38));
        assertEquals(5, binarySearchAlternative(arr, 44));
        assertEquals(6, binarySearchAlternative(arr, 52));
        assertEquals(7, binarySearchAlternative(arr, 53));
    }

    @Test
    @DisplayName("没找到")
    public void test4() {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(-1, binarySearchAlternative(arr, 0));
        assertEquals(-1, binarySearchAlternative(arr, 15));
        assertEquals(-1, binarySearchAlternative(arr, 60));
    }

    @Test
    @DisplayName("找到")
    public void test5() {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(0, binarySearchBalance(arr, 7));
        assertEquals(1, binarySearchBalance(arr, 13));
        assertEquals(2, binarySearchBalance(arr, 21));
        assertEquals(3, binarySearchBalance(arr, 30));
        assertEquals(4, binarySearchBalance(arr, 38));
        assertEquals(5, binarySearchBalance(arr, 44));
        assertEquals(6, binarySearchBalance(arr, 52));
        assertEquals(7, binarySearchBalance(arr, 53));
    }

    @Test
    @DisplayName("没找到")
    public void test6() {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(-1, binarySearchBalance(arr, 0));
        assertEquals(-1, binarySearchBalance(arr, 15));
        assertEquals(-1, binarySearchBalance(arr, 60));
    }

    @Test
    @DisplayName("Java版二分查找 内部实现")
    public void test7() {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
        int target = 15;
        int i = Arrays.binarySearch(arr, target);
        // 返回值 -插入点+1
        System.out.println(i);
        if (i < 0){
            int insertIndex = Math.abs(i + 1);
            int[] b = new int[arr.length+1];
            System.arraycopy(arr,0,b,0,insertIndex);
            b[insertIndex] = target;
            System.arraycopy(arr,insertIndex,b,insertIndex+1, arr.length-insertIndex);
            System.out.println(Arrays.toString(b));
        }
    }

    @Test
    @DisplayName("测试二分查找 查找出现在最左边的元素")
    public void test8() {
        int[] arr = {1, 2, 4, 4, 4, 5, 6, 7};
        assertEquals(0, binarySearchLeftmost1(arr, 1));
        assertEquals(1, binarySearchLeftmost1(arr, 2));
        assertEquals(2, binarySearchLeftmost1(arr, 4));
        assertEquals(5, binarySearchLeftmost1(arr, 5));
        assertEquals(6, binarySearchLeftmost1(arr, 6));
        assertEquals(7, binarySearchLeftmost1(arr, 7));

        assertEquals(-1, binarySearchLeftmost1(arr, 0));
        assertEquals(-1, binarySearchLeftmost1(arr, 3));
        assertEquals(-1, binarySearchLeftmost1(arr, 8));
    }

    @Test
    @DisplayName("测试二分查找 查找出现在最右边的元素")
    public void test9() {
        int[] arr = {1, 2, 4, 4, 4, 5, 6, 7};
        assertEquals(0, binarySearchRightmost1(arr, 1));
        assertEquals(1, binarySearchRightmost1(arr, 2));
        assertEquals(4, binarySearchRightmost1(arr, 4));
        assertEquals(5, binarySearchRightmost1(arr, 5));
        assertEquals(6, binarySearchRightmost1(arr, 6));
        assertEquals(7, binarySearchRightmost1(arr, 7));

        assertEquals(-1, binarySearchRightmost1(arr, 0));
        assertEquals(-1, binarySearchRightmost1(arr, 3));
        assertEquals(-1, binarySearchRightmost1(arr, 8));
    }
}
